using System;
using System.Collections.Generic;

// 图 BFS/DFS 测试类
public class GraphBFSDFSTest
{
    public static void RunTest()
    {
        Console.WriteLine("========== 图 BFS/DFS 测试 ==========");
        //测试
        DirectedWeightedGraph graph = new(5);
        graph.AddEdge(0, 1, 1);
        graph.AddEdge(0, 2, 2);
        graph.AddEdge(0, 3, 3);
        graph.AddEdge(1, 4, 14);
        graph.AddEdge(4, 2, 42);
        graph.AddEdge(4, 3, 43);

        GraphDFS graphDFS = new();
        GraphBFS graphBFS = new();

        Console.WriteLine("\n========== BFS 遍历 ==========");
        graphBFS.BFS(graph, 0);

        Console.WriteLine("\n按 Enter 键继续测试...");
        Console.ReadLine();

        Console.WriteLine("\n========== DFS 路径查找 ==========");
        graphDFS.TraversePath(graph, 0, 2);
    }
}

/// <summary>
/// 深度遍历:特点是一条路走到黑 O(E+V)
/// </summary>
public class GraphDFS{
    //遍历所有节点(以有向权图邻接表形式举例)
    public void TraverseVertex(DirectedWeightedGraph graph, int currentVertex, bool[] visited){
        if(currentVertex < 0 || currentVertex >= graph.GetVertexCount()) return;

        if(visited[currentVertex]) return;

        //前序位置
        //Debug.Log("前序位置: " + currentVertex);
        visited[currentVertex] = true;
        foreach(var edge in graph.GetNeighbors(currentVertex)){
            TraverseVertex(graph, edge.to, visited);
        }
        //后序位置
         Console.WriteLine("前序位置: " + currentVertex);

    }

    // 遍历所有路径 - 
    public void TraversePath(DirectedWeightedGraph graph, int src, int dest){
        bool[] onPath = new bool[graph.GetVertexCount()]; //记录已访问的节点
        List<int> path = new (); //记录路径
        TraversePathHelper(graph, src, dest, onPath, path);
    }
    
    private void TraversePathHelper(DirectedWeightedGraph graph, int cur, int dest,  bool[] onPath, List<int> path){
        if(cur < 0 || cur >= graph.GetVertexCount()) return;
        if(onPath[cur]) return; // 防止死循环
        
        if(cur == dest){
            Console.WriteLine("找到路径: " + string.Join(" -> ", path) + " -> " + dest);
            return;
        }
        
        // 前序位置
        onPath[cur] = true;
        path.Add(cur);
        
        foreach(var edge in graph.GetNeighbors(cur)){
            TraversePathHelper(graph, edge.to, dest, onPath, path);
        }
        
        // 后序位置 - 回溯
        path.RemoveAt(path.Count - 1);  // 移除当前节点
        onPath[cur] = false;            // 取消路径标记
    }


    //遍历所有边 不太常见(以有向权图邻接表形式举例)
    public void TraverseEdge( Vertex currentVertex, bool[][] visited){
        if(currentVertex == null) return;

        foreach(var neighbor in currentVertex.neighbors){
            //如果这条边已经被访问过，则跳过
            if(visited[currentVertex.id][neighbor.id]) continue;
            //前序位置
            Console.WriteLine("前序位置: " + currentVertex.id + " -> " + neighbor.id);
            //标记这条边已经访问过
            visited[currentVertex.id][neighbor.id] = true;
            TraverseEdge(neighbor, visited);
            //后序位置
            // Debug.Log("前序位置: " + currentVertex);
        }

    }
}

/// <summary>
/// 广度优先遍历:特点是一层一层遍历 O(E+V)
/// </summary>
public class GraphBFS{
    
    public class State {
        public int node;    // 当前节点ID
        public int step;    // 从起点到当前节点的遍历步数
        
        public State(int node, int step) {
            this.node = node;
            this.step = step;
        }
    }
    
    // 图结构的BFS遍历，从节点s开始进行BFS，且记录遍历步数
    public void BFS(DirectedWeightedGraph graph, int s) {
        bool[] visited = new bool[graph.GetVertexCount()];
        Queue<State> queue = new Queue<State>();
        
        // 将起点加入队列，步数为0
        queue.Enqueue(new State(s, 0));
        visited[s] = true;
        
        while (queue.Count > 0) {
            State state = queue.Dequeue();
            int cur = state.node;
            int step = state.step;
            
            Console.WriteLine($"访问节点 {cur}，步数 {step}");
            
            // 遍历当前节点的所有邻居
            foreach (var edge in graph.GetNeighbors(cur)) {
                if (visited[edge.to]) {
                    continue; // 已访问过，跳过
                }
                
                // 将邻居节点加入队列，步数+1
                queue.Enqueue(new State(edge.to, step + 1));
                visited[edge.to] = true;
            }
        }
    }
}

